SherbyNet - /page/wikibook/entry.mu

Micron Document

<!DOCTYPE html>

<title>Search algorithm</title>

</head>

<span id="openzim-page-title" class="mw-page-title-main"><span class="mw-page-title-main">Search algorithm</span></span>

</h1>

</header>

/* start https://en.wikipedia.org/ */

.mw-parser-output .ambox{border:1px solid #a2a9b1;border-left:10px solid #36c;background-color:#fbfbfb;box-sizing:border-box}.mw-parser-output .ambox+link+.ambox,.mw-parser-output .ambox+link+style+.ambox,.mw-parser-output .ambox+link+link+.ambox,.mw-parser-output .ambox+.mw-empty-elt+link+.ambox,.mw-parser-output .ambox+.mw-empty-elt+link+style+.ambox,.mw-parser-output .ambox+.mw-empty-elt+link+link+.ambox{margin-top:-1px}html body.mediawiki .mw-parser-output .ambox.mbox-small-left{margin:4px 1em 4px 0;overflow:hidden;width:238px;border-collapse:collapse;font-size:88%;line-height:1.25em}.mw-parser-output .ambox-speedy{border-left:10px solid #b32424;background-color:#fee7e6}.mw-parser-output .ambox-delete{border-left:10px solid #b32424}.mw-parser-output .ambox-content{border-left:10px solid #f28500}.mw-parser-output .ambox-style{border-left:10px solid #fc3}.mw-parser-output .ambox-move{border-left:10px solid #9932cc}.mw-parser-output .ambox-protection{border-left:10px solid #a2a9b1}.mw-parser-output .ambox .mbox-text{border:none;padding:0.25em 0.5em;width:100%}.mw-parser-output .ambox .mbox-image{border:none;padding:2px 0 2px 0.5em;text-align:center}.mw-parser-output .ambox .mbox-imageright{border:none;padding:2px 0.5em 2px 0;text-align:center}.mw-parser-output .ambox .mbox-empty-cell{border:none;padding:0;width:1px}.mw-parser-output .ambox .mbox-image-div{width:52px}@media(min-width:720px){.mw-parser-output .ambox{margin:0 10%}}@media print{body.ns-0 .mw-parser-output .ambox{display:none!important}}

/* end https://en.wikipedia.org/ */

</style><style data-mw-deduplicate="TemplateStyles:r1248332772">

/* start https://en.wikipedia.org/ */

.mw-parser-output .multiple-issues-text{width:95%;margin:0.2em 0}.mw-parser-output .multiple-issues-text>.mw-collapsible-content{margin-top:0.3em}.mw-parser-output .compact-ambox .ambox{border:none;border-collapse:collapse;background-color:transparent;margin:0 0 0 1.6em!important;padding:0!important;width:auto;display:block}body.mediawiki .mw-parser-output .compact-ambox .ambox.mbox-small-left{font-size:100%;width:auto;margin:0}.mw-parser-output .compact-ambox .ambox .mbox-text{padding:0!important;margin:0!important}.mw-parser-output .compact-ambox .ambox .mbox-text-span{display:list-item;line-height:1.5em;list-style-type:disc}body.skin-minerva .mw-parser-output .multiple-issues-text>.mw-collapsible-toggle,.mw-parser-output .compact-ambox .ambox .mbox-image,.mw-parser-output .compact-ambox .ambox .mbox-imageright,.mw-parser-output .compact-ambox .ambox .mbox-empty-cell,.mw-parser-output .compact-ambox .hide-when-compact{display:none}

/* end https://en.wikipedia.org/ */

</style>

<p>In <a href="Computer_science" title="Computer science">computer science</a>, a <b>search algorithm</b> is an <a href="Algorithm" title="Algorithm">algorithm</a> designed to solve a <a href="Search_problem" title="Search problem">search problem</a>. Search algorithms work to retrieve information stored within particular <a href="Data_structure" title="Data structure">data structure</a>, or calculated in the <a href="Feasible_region" title="Feasible region">search space</a> of a problem domain, with <a href="Continuous_or_discrete_variable" title="Continuous or discrete variable">either discrete or continuous values</a>.

</p><p>Although <a href="Search_engine_(computing)" title="Search engine (computing)">search engines</a> use search algorithms, they belong to the study of <a href="Information_retrieval" title="Information retrieval">information retrieval</a>, not algorithmics.

</p><p>The appropriate search algorithm to use often depends on the data structure being searched, and may also include prior knowledge about the data. Search algorithms can be made faster or more efficient by specially constructed database structures, such as <a href="Search_tree" title="Search tree">search trees</a>, <a href="Hash_map" class="mw-redirect" title="Hash map">hash maps</a>, and <a href="Database_index" title="Database index">database indexes</a>.<sup id="cite_ref-FOOTNOTEBeameFich200239_1-0" class="reference"><a href="#cite_note-FOOTNOTEBeameFich200239-1"><span class="cite-bracket">[</span>1<span class="cite-bracket">]</span></a></sup><sup id="cite_ref-FOOTNOTEKnuth1998§6.5_("Retrieval_on_Secondary_Keys")_2-0" class="reference"><a href="#cite_note-FOOTNOTEKnuth1998§6.5_("Retrieval_on_Secondary_Keys")-2"><span class="cite-bracket">[</span>2<span class="cite-bracket">]</span></a></sup>

</p><p>Search algorithms can be classified based on their mechanism of searching into three types of algorithms: linear, binary, and hashing. <a href="Linear_search" title="Linear search">Linear search</a> algorithms check every record for the one associated with a target key in a linear fashion.<sup id="cite_ref-FOOTNOTEKnuth1998§6.1_("Sequential_Searching")_3-0" class="reference"><a href="#cite_note-FOOTNOTEKnuth1998§6.1_("Sequential_Searching")-3"><span class="cite-bracket">[</span>3<span class="cite-bracket">]</span></a></sup> <a href="Binary_search_algorithm" class="mw-redirect" title="Binary search algorithm">Binary, or half-interval, searches</a> repeatedly target the center of the search structure and divide the search space in half. Comparison search algorithms improve on linear searching by successively eliminating records based on comparisons of the keys until the target record is found, and can be applied on data structures with a defined order.<sup id="cite_ref-FOOTNOTEKnuth1998§6.2_("Searching_by_Comparison_of_Keys")_4-0" class="reference"><a href="#cite_note-FOOTNOTEKnuth1998§6.2_("Searching_by_Comparison_of_Keys")-4"><span class="cite-bracket">[</span>4<span class="cite-bracket">]</span></a></sup> Digital search algorithms work based on the properties of digits in data structures by using numerical keys.<sup id="cite_ref-FOOTNOTEKnuth1998§6.3_(Digital_Searching)_5-0" class="reference"><a href="#cite_note-FOOTNOTEKnuth1998§6.3_(Digital_Searching)-5"><span class="cite-bracket">[</span>5<span class="cite-bracket">]</span></a></sup> Finally, <a href="Hash_table" title="Hash table">hashing</a> directly maps keys to records based on a <a href="Hash_function" title="Hash function">hash function</a>.<sup id="cite_ref-FOOTNOTEKnuth1998§6.4,_(Hashing)_6-0" class="reference"><a href="#cite_note-FOOTNOTEKnuth1998§6.4,_(Hashing)-6"><span class="cite-bracket">[</span>6<span class="cite-bracket">]</span></a></sup>

</p><p>Algorithms are often evaluated by their <a href="Computational_complexity" title="Computational complexity">computational complexity</a>, or maximum theoretical run time. Binary search functions, for example, have a maximum complexity of <span class="texhtml"><i>O</i>(log <i>n</i>)</span>, or logarithmic time. In simple terms, the maximum number of operations needed to find the search target is a logarithmic function of the size of the search space.

</p>

<div class="mw-heading mw-heading2"><h2 id="Applications_of_search_algorithms">Applications of search algorithms</h2></div>

<p>Specific applications of search algorithms include:

</p>

<ul><li>Problems in <a href="Combinatorial_optimization" title="Combinatorial optimization">combinatorial optimization</a>, such as:

<ul><li>The <a href="Vehicle_routing_problem" title="Vehicle routing problem">vehicle routing problem</a>, a form of <a href="Shortest_path_problem" title="Shortest path problem">shortest path problem</a></li>

<li>The <a href="Knapsack_problem" title="Knapsack problem">knapsack problem</a>: Given a set of items, each with a weight and a value, determine the number of each item to include in a collection so that the total weight is less than or equal to a given limit and the total value is as large as possible.</li>

<li>The <a href="Nurse_scheduling_problem" title="Nurse scheduling problem">nurse scheduling problem</a></li></ul></li>

<li>Problems in <a href="Constraint_satisfaction" title="Constraint satisfaction">constraint satisfaction</a>, such as:

<ul><li>The <a href="Map_coloring_problem" class="mw-redirect" title="Map coloring problem">map coloring problem</a></li>

<li>Filling in a <a href="Sudoku" title="Sudoku">sudoku</a> or <a href="Crossword_puzzle" class="mw-redirect" title="Crossword puzzle">crossword puzzle</a></li></ul></li>

<li>In <a href="Game_theory" title="Game theory">game theory</a> and especially <a href="Combinatorial_game_theory" title="Combinatorial game theory">combinatorial game theory</a>, choosing the best move to make next (such as with the <a href="Minmax" class="mw-redirect" title="Minmax">minmax</a> algorithm)</li>

<li>Finding a combination or password from the whole set of possibilities</li>

<li><a href="Factorization" title="Factorization">Factoring</a> an integer (an important problem in <a href="Cryptography" title="Cryptography">cryptography</a>)</li>

<li>Search engine optimization (SEO) and content optimization for web crawlers</li>

<li>Optimizing an industrial process, such as a <a href="Chemical_reaction" title="Chemical reaction">chemical reaction</a>, by changing the parameters of the process (like temperature, pressure, and pH)</li>

<li>Retrieving a record from a <a href="Database" title="Database">database</a></li>

<li>Finding the maximum or minimum value in a <a href="List_(abstract_data_type)" title="List (abstract data type)">list</a> or <a href="Array_data_structure" class="mw-redirect" title="Array data structure">array</a></li>

<li>Checking to see if a given value is present in a set of values</li></ul>

<div class="mw-heading mw-heading2"><h2 id="Classes">Classes</h2></div>

<div class="mw-heading mw-heading3"><h3 id="For_virtual_search_spaces">For virtual search spaces</h3></div>

/* start https://en.wikipedia.org/ */

.mw-parser-output .hatnote{font-style:italic}.mw-parser-output div.hatnote{padding-left:1.6em;margin-bottom:0.5em}.mw-parser-output .hatnote i{font-style:normal}.mw-parser-output .hatnote+link+.hatnote{margin-top:-0.5em}@media print{body.ns-0 .mw-parser-output .hatnote{display:none!important}}

/* end https://en.wikipedia.org/ */

</style><div role="note" class="hatnote navigation-not-searchable">See also: <a href="Solver" title="Solver">Solver</a></div>

<p>Algorithms for searching virtual spaces are used in the <a href="Constraint_satisfaction_problem" title="Constraint satisfaction problem">constraint satisfaction problem</a>, where the goal is to find a set of value assignments to certain variables that will satisfy specific mathematical <a href="Equation" title="Equation">equations</a> and <a href="Inequation" title="Inequation">inequations</a> / equalities. They are also used when the goal is to find a variable assignment that will <a href="Discrete_optimization" title="Discrete optimization">maximize or minimize</a> a certain function of those variables. Algorithms for these problems include the basic <a href="Brute-force_search" title="Brute-force search">brute-force search</a> (also called "naïve" or "uninformed" search), and a variety of <a href="Heuristic_function" class="mw-redirect" title="Heuristic function">heuristics</a> that try to exploit partial knowledge about the structure of this space, such as linear relaxation, constraint generation, and <a href="Local_consistency" title="Local consistency">constraint propagation</a>.

</p><p>An important subclass are the <a href="Local_search_(optimization)" title="Local search (optimization)">local search</a> methods, that view the elements of the search space as the <a href="Vertex_(graph_theory)" title="Vertex (graph theory)">vertices</a> of a graph, with edges defined by a set of heuristics applicable to the case; and scan the space by moving from item to item along the edges, for example according to the <a href="Gradient_descent" title="Gradient descent">steepest descent</a> or <a href="Best-first_search" title="Best-first search">best-first</a> criterion, or in a <a href="Stochastic_optimization" title="Stochastic optimization">stochastic search</a>. This category includes a great variety of general <a href="Metaheuristic" title="Metaheuristic">metaheuristic</a> methods, such as <a href="Simulated_annealing" title="Simulated annealing">simulated annealing</a>, <a href="Tabu_search" title="Tabu search">tabu search</a>, A-teams <sup id="cite_ref-7" class="reference"><a href="#cite_note-7"><span class="cite-bracket">[</span>7<span class="cite-bracket">]</span></a></sup>, and <a href="Genetic_programming" title="Genetic programming">genetic programming</a>, that combine arbitrary heuristics in specific ways. The opposite of local search would be global search methods. This method is applicable when the search space is not limited and all aspects of the given network are available to the entity running the search algorithm.<sup id="cite_ref-8" class="reference"><a href="#cite_note-8"><span class="cite-bracket">[</span>8<span class="cite-bracket">]</span></a></sup>

</p><p>This class also includes various <a href="Tree_traversal" title="Tree traversal">tree search algorithms</a>, that view the elements as vertices of a <a href="Tree_(graph_theory)" title="Tree (graph theory)">tree</a>, and traverse that tree in some special order. Examples of the latter include the exhaustive methods such as <a href="Depth-first_search" title="Depth-first search">depth-first search</a> and <a href="Breadth-first_search" title="Breadth-first search">breadth-first search</a>, as well as various heuristic-based <a href="Pruning_(decision_trees)" class="mw-redirect" title="Pruning (decision trees)">search tree pruning</a> methods such as <a href="Backtracking" title="Backtracking">backtracking</a> and <a href="Branch_and_bound" title="Branch and bound">branch and bound</a>. Unlike general metaheuristics, which at best work only in a probabilistic sense, many of these tree-search methods are guaranteed to find the exact or optimal solution, if given enough time. This is called "<a href="Completeness_(logic)" title="Completeness (logic)">completeness</a>".

</p><p>Another important sub-class consists of algorithms for exploring the <a href="Game_tree" title="Game tree">game tree</a> of multiple-player games, such as <a href="Chess" title="Chess">chess</a> or <a href="Backgammon" title="Backgammon">backgammon</a>, whose nodes consist of all possible game situations that could result from the current situation. The goal in these problems is to find the move that provides the best chance of a win, taking into account all possible moves of the opponent(s). Similar problems occur when humans or machines have to make successive decisions whose outcomes are not entirely under one's control, such as in <a href="Robot" title="Robot">robot</a> guidance or in <a href="Marketing" title="Marketing">marketing</a>, <a href="Finance" title="Finance">financial</a>, or <a href="Military" title="Military">military</a> strategy planning. This kind of problem — <a href="Combinatorial_search" title="Combinatorial search">combinatorial search</a> — has been extensively studied in the context of <a href="Artificial_intelligence" title="Artificial intelligence">artificial intelligence</a>. Examples of algorithms for this class are the <a href="Minimax" title="Minimax">minimax algorithm</a>, <a href="Alpha%E2%80%93beta_pruning" title="Alpha–beta pruning">alpha–beta pruning</a>, and the <a href="A*_search_algorithm" title="A* search algorithm">A* algorithm</a> and its variants.

</p>

<div class="mw-heading mw-heading3"><h3 id="For_sub-structures_of_a_given_structure">For sub-structures of a given structure</h3></div>

<p>An important and extensively studied subclass are the <a href="List_of_algorithms#Graph_algorithms" title="List of algorithms">graph algorithms</a>, in particular <a href="Graph_traversal" title="Graph traversal">graph traversal</a> algorithms, for finding specific sub-structures in a given graph — such as <a href="Glossary_of_graph_theory#Subgraphs" title="Glossary of graph theory">subgraphs</a>, <a href="Path_(graph_theory)" title="Path (graph theory)">paths</a>, circuits, and so on. Examples include <a href="Dijkstra's_algorithm" title="Dijkstra's algorithm">Dijkstra's algorithm</a>, <a href="Kruskal's_algorithm" title="Kruskal's algorithm">Kruskal's algorithm</a>, the <a href="Nearest_neighbour_algorithm" title="Nearest neighbour algorithm">nearest neighbour algorithm</a>, and <a href="Prim's_algorithm" title="Prim's algorithm">Prim's algorithm</a>.

</p><p>Another important subclass of this category are the <a href="String_searching_algorithm" class="mw-redirect" title="String searching algorithm">string searching algorithms</a>, that search for patterns within strings. Two famous examples are the <a href="Boyer%E2%80%93Moore_string-search_algorithm" title="Boyer–Moore string-search algorithm">Boyer–Moore</a> and <a href="Knuth%E2%80%93Morris%E2%80%93Pratt_algorithm" title="Knuth–Morris–Pratt algorithm">Knuth–Morris–Pratt algorithms</a>, and several algorithms based on the <a href="Suffix_tree" title="Suffix tree">suffix tree</a> data structure.

</p>

<div class="mw-heading mw-heading3"><h3 id="Search_for_the_maximum_of_a_function">Search for the maximum of a function</h3></div>

<p>In 1953, American <a href="Statistics" title="Statistics">statistician</a> <a href="Jack_Kiefer_(statistician)" title="Jack Kiefer (statistician)">Jack Kiefer</a> devised <a href="Fibonacci_search_technique" title="Fibonacci search technique">Fibonacci search</a> which can be used to find the maximum of a unimodal function and has many other applications in computer science.

</p>

<div class="mw-heading mw-heading3"><h3 id="For_quantum_computers">For quantum computers</h3></div>

<p>There are also search methods designed for <a href="Quantum_computing" title="Quantum computing">quantum computers</a>, like <a href="Grover's_algorithm" title="Grover's algorithm">Grover's algorithm</a>, that are theoretically faster than linear or brute-force search even without the help of data structures or heuristics. While the ideas and applications behind quantum computers are still entirely theoretical, studies have been conducted with algorithms like Grover's that accurately replicate the hypothetical physical versions of quantum computing systems.<sup id="cite_ref-9" class="reference"><a href="#cite_note-9"><span class="cite-bracket">[</span>9<span class="cite-bracket">]</span></a></sup>

</p>

<ul><li><a href="Backward_induction" title="Backward induction">Backward induction</a> – Process of reasoning backwards in sequence</li>

<li><a href="Content-addressable_memory" title="Content-addressable memory">Content-addressable memory</a> – Type of computer memory hardware</li>

<li><a href="Dual-phase_evolution" title="Dual-phase evolution">Dual-phase evolution</a> – Process that drives self-organization within complex adaptive systems</li>

<li><a href="Linear_search_problem" title="Linear search problem">Linear search problem</a> – Computational search problem</li>

<li><a href="No_free_lunch_in_search_and_optimization" title="No free lunch in search and optimization">No free lunch in search and optimization</a> – Average solution cost is the same with any method</li>

<li><a href="Recommender_system" title="Recommender system">Recommender system</a> – System to predict users' preferences, also use statistical methods to rank results in very large data sets</li>

<li><a href="Search_engine_(computing)" title="Search engine (computing)">Search engine (computing)</a> – System to help searching for information</li>

<li><a href="Search_game" title="Search game">Search game</a> – Two-person zero-sum game</li>

<li><a href="Selection_algorithm" title="Selection algorithm">Selection algorithm</a> – Method for finding kth smallest value</li>

<li><a href="Solver" title="Solver">Solver</a> – Software for a class of mathematical problems</li>

<li><a href="Sorting_algorithm" title="Sorting algorithm">Sorting algorithm</a> – Algorithm that arranges lists in order, necessary for executing certain search algorithms</li>

<li><a href="Web_search_engine" class="mw-redirect" title="Web search engine">Web search engine</a> – Software system for finding relevant information on the Web<span style="display:none" class="category-annotation-with-redirected-description">Pages displaying short descriptions of redirect targets</span></li></ul>

<p>Categories:

</p>

<ul><li>Category:Search algorithms</li></ul>

<div class="mw-heading mw-heading2"><h2 id="References">References</h2></div>

<div class="mw-heading mw-heading3"><h3 id="Citations">Citations</h3></div>

/* start https://en.wikipedia.org/ */

.mw-parser-output .reflist{margin-bottom:0.5em;list-style-type:decimal}@media screen{.mw-parser-output .reflist{font-size:90%}}.mw-parser-output .reflist .references{font-size:100%;margin-bottom:0;list-style-type:inherit}.mw-parser-output .reflist-columns-2{column-width:30em}.mw-parser-output .reflist-columns-3{column-width:25em}.mw-parser-output .reflist-columns{margin-top:0.3em}.mw-parser-output .reflist-columns ol{margin-top:0}.mw-parser-output .reflist-columns li{page-break-inside:avoid;break-inside:avoid-column}.mw-parser-output .reflist-upper-alpha{list-style-type:upper-alpha}.mw-parser-output .reflist-upper-roman{list-style-type:upper-roman}.mw-parser-output .reflist-lower-alpha{list-style-type:lower-alpha}.mw-parser-output .reflist-lower-greek{list-style-type:lower-greek}.mw-parser-output .reflist-lower-roman{list-style-type:lower-roman}

/* end https://en.wikipedia.org/ */

</style><div class="reflist reflist-columns references-column-width" style="column-width: 30em;">

<li id="cite_note-FOOTNOTEBeameFich200239-1"><span class="mw-cite-backlink"><b><a href="#cite_ref-FOOTNOTEBeameFich200239_1-0">^</a></b></span> <span class="reference-text"><a href="#CITEREFBeameFich2002">Beame & Fich 2002</a>, p. 39.</span>

</li>

<li id="cite_note-FOOTNOTEKnuth1998§6.5_("Retrieval_on_Secondary_Keys")-2"><span class="mw-cite-backlink"><b><a href="#cite_ref-FOOTNOTEKnuth1998§6.5_("Retrieval_on_Secondary_Keys")_2-0">^</a></b></span> <span class="reference-text"><a href="#CITEREFKnuth1998">Knuth 1998</a>, §6.5 ("Retrieval on Secondary Keys").</span>

</li>

<li id="cite_note-FOOTNOTEKnuth1998§6.1_("Sequential_Searching")-3"><span class="mw-cite-backlink"><b><a href="#cite_ref-FOOTNOTEKnuth1998§6.1_("Sequential_Searching")_3-0">^</a></b></span> <span class="reference-text"><a href="#CITEREFKnuth1998">Knuth 1998</a>, §6.1 ("Sequential Searching").</span>

</li>

<li id="cite_note-FOOTNOTEKnuth1998§6.2_("Searching_by_Comparison_of_Keys")-4"><span class="mw-cite-backlink"><b><a href="#cite_ref-FOOTNOTEKnuth1998§6.2_("Searching_by_Comparison_of_Keys")_4-0">^</a></b></span> <span class="reference-text"><a href="#CITEREFKnuth1998">Knuth 1998</a>, §6.2 ("Searching by Comparison of Keys").</span>

</li>

<li id="cite_note-FOOTNOTEKnuth1998§6.3_(Digital_Searching)-5"><span class="mw-cite-backlink"><b><a href="#cite_ref-FOOTNOTEKnuth1998§6.3_(Digital_Searching)_5-0">^</a></b></span> <span class="reference-text"><a href="#CITEREFKnuth1998">Knuth 1998</a>, §6.3 (Digital Searching).</span>

</li>

<li id="cite_note-FOOTNOTEKnuth1998§6.4,_(Hashing)-6"><span class="mw-cite-backlink"><b><a href="#cite_ref-FOOTNOTEKnuth1998§6.4,_(Hashing)_6-0">^</a></b></span> <span class="reference-text"><a href="#CITEREFKnuth1998">Knuth 1998</a>, §6.4, (Hashing).</span>

</li>

/* start https://en.wikipedia.org/ */

.mw-parser-output cite.citation{font-style:inherit;word-wrap:break-word}.mw-parser-output .citation q{quotes:"\"""\"""'""'"}.mw-parser-output .citation:target{background-color:rgba(0,127,255,0.133)}.mw-parser-output .id-lock-free.id-lock-free a{background:url("./mw/Lock-green.svg")right 0.1em center/9px no-repeat}.mw-parser-output .id-lock-limited.id-lock-limited a,.mw-parser-output .id-lock-registration.id-lock-registration a{background:url("./mw/Lock-gray-alt-2.svg")right 0.1em center/9px no-repeat}.mw-parser-output .id-lock-subscription.id-lock-subscription a{background:url("./mw/Lock-red-alt-2.svg")right 0.1em center/9px no-repeat}.mw-parser-output .cs1-ws-icon a{background:url("./mw/Wikisource-logo.svg")right 0.1em center/12px no-repeat}body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .id-lock-free a,body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .id-lock-limited a,body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .id-lock-registration a,body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .id-lock-subscription a,body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .cs1-ws-icon a{background-size:contain;padding:0 1em 0 0}.mw-parser-output .cs1-code{color:inherit;background:inherit;border:none;padding:inherit}.mw-parser-output .cs1-hidden-error{display:none;color:var(--color-error,#d33)}.mw-parser-output .cs1-visible-error{color:var(--color-error,#d33)}.mw-parser-output .cs1-maint{display:none;color:#085;margin-left:0.3em}.mw-parser-output .cs1-kern-left{padding-left:0.2em}.mw-parser-output .cs1-kern-right{padding-right:0.2em}.mw-parser-output .citation .mw-selflink{font-weight:inherit}@media screen{.mw-parser-output .cs1-format{font-size:95%}html.skin-theme-clientpref-night .mw-parser-output .cs1-maint{color:#18911f}}@media screen and (prefers-color-scheme:dark){html.skin-theme-clientpref-os .mw-parser-output .cs1-maint{color:#18911f}}

/* end https://en.wikipedia.org/ */

</style><cite id="CITEREFTalukdarBaerentzenGoveDe_Souza1998" class="citation journal cs1">Talukdar, Sarosh; Baerentzen, Lars; Gove, Andrew; De Souza, Pedro (1998-12-01). <a rel="nofollow" class="external text" href="https://doi.org/10.1023/A:1009669824615">"Asynchronous Teams: Cooperation Schemes for Autonomous Agents"</a>. <i>Journal of Heuristics</i>. <b>4</b> (4): <span class="nowrap">295–</span>321. <a href="Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1023%2FA%3A1009669824615">10.1023/A:1009669824615</a>. <a href="ISSN_(identifier)" class="mw-redirect" title="ISSN (identifier)">ISSN</a> <a rel="nofollow" class="external text" href="https://search.worldcat.org/issn/1572-9397">1572-9397</a>.</cite></span>

</li>

<li id="cite_note-8"><span class="mw-cite-backlink"><b><a href="#cite_ref-8">^</a></b></span> <span class="reference-text"><cite id="CITEREFHunterPippenger2013" class="citation journal cs1">Hunter, A.H.; Pippenger, Nicholas (4 July 2013). "Local versus global search in channel graphs". <i>Networks: An International Journey</i>. <a href="ArXiv_(identifier)" class="mw-redirect" title="ArXiv (identifier)">arXiv</a>:<span class="id-lock-free" title="Freely accessible"><a rel="nofollow" class="external text" href="https://arxiv.org/abs/1004.2526">1004.2526</a></span>.</cite></span>

</li>

<li id="cite_note-9"><span class="mw-cite-backlink"><b><a href="#cite_ref-9">^</a></b></span> <span class="reference-text"><cite id="CITEREFLópezGorinLara2008" class="citation journal cs1">López, G V; Gorin, T; Lara, L (26 February 2008). "Simulation of Grover's quantum search algorithm in an Ising-nuclear-spin-chain quantum computer with first- and second-nearest-neighbour couplings". <i>Journal of Physics B: Atomic, Molecular and Optical Physics</i>. <b>41</b> (5): 055504. <a href="ArXiv_(identifier)" class="mw-redirect" title="ArXiv (identifier)">arXiv</a>:<span class="id-lock-free" title="Freely accessible"><a rel="nofollow" class="external text" href="https://arxiv.org/abs/0710.3196">0710.3196</a></span>. <a href="Bibcode_(identifier)" class="mw-redirect" title="Bibcode (identifier)">Bibcode</a>:<a rel="nofollow" class="external text" href="https://ui.adsabs.harvard.edu/abs/2008JPhB...41e5504L">2008JPhB...41e5504L</a>. <a href="Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1088%2F0953-4075%2F41%2F5%2F055504">10.1088/0953-4075/41/5/055504</a>. <a href="S2CID_(identifier)" class="mw-redirect" title="S2CID (identifier)">S2CID</a> <a rel="nofollow" class="external text" href="https://api.semanticscholar.org/CorpusID:18796310">18796310</a>.</cite></span>

</li>

</ol></div>

<div class="mw-heading mw-heading3"><h3 id="Bibliography">Bibliography</h3></div>

<div class="mw-heading mw-heading4"><h4 id="Books">Books</h4></div>

<ul><li><cite id="CITEREFKnuth1998" class="citation book cs1"><a href="Donald_Knuth" title="Donald Knuth">Knuth, Donald</a> (1998). <i>Sorting and Searching</i>. <a href="The_Art_of_Computer_Programming" title="The Art of Computer Programming">The Art of Computer Programming</a>. Vol. 3 (2nd ed.). Reading, MA: Addison-Wesley Professional.</cite></li></ul>

<div class="mw-heading mw-heading4"><h4 id="Articles">Articles</h4></div>

<ul><li><cite id="CITEREFBeameFich2002" class="citation journal cs1">Beame, Paul; <a href="Faith_Ellen" title="Faith Ellen">Fich, Faith</a> (August 2002). <a rel="nofollow" class="external text" href="https://doi.org/10.1006%2Fjcss.2002.1822">"Optimal Bounds for the Predecessor Problem and Related Problems"</a>. <i><a href="Journal_of_Computer_and_System_Sciences" title="Journal of Computer and System Sciences">Journal of Computer and System Sciences</a></i>. <b>65</b> (1): <span class="nowrap">38–</span>72. <a href="Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<span class="id-lock-free" title="Freely accessible"><a rel="nofollow" class="external text" href="https://doi.org/10.1006%2Fjcss.2002.1822">10.1006/jcss.2002.1822</a></span>. <a href="S2CID_(identifier)" class="mw-redirect" title="S2CID (identifier)">S2CID</a> <a rel="nofollow" class="external text" href="https://api.semanticscholar.org/CorpusID:1991980">1991980</a>.</cite></li>

<li><cite class="citation journal cs1">Schmittou, Thomas; Schmittou, Faith E. (2002-08-01). <a rel="nofollow" class="external text" href="https://doi.org/10.1006%2Fjcss.2002.1822">"Optimal Bounds for the Predecessor Problem and Related Problems"</a>. <i>Journal of Computer and System Sciences</i>. <b>65</b> (1): <span class="nowrap">38–</span>72. <a href="Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<span class="id-lock-free" title="Freely accessible"><a rel="nofollow" class="external text" href="https://doi.org/10.1006%2Fjcss.2002.1822">10.1006/jcss.2002.1822</a></span>.</cite></li></ul>

<div class="mw-heading mw-heading2"><h2 id="External_links">External links</h2></div>

/* start https://en.wikipedia.org/ */

.mw-parser-output .refbegin{margin-bottom:0.5em}.mw-parser-output .refbegin-hanging-indents>ul{margin-left:0}.mw-parser-output .refbegin-hanging-indents>ul>li{margin-left:0;padding-left:3.2em;text-indent:-3.2em}.mw-parser-output .refbegin-hanging-indents ul,.mw-parser-output .refbegin-hanging-indents ul li{list-style:none}@media(max-width:720px){.mw-parser-output .refbegin-hanging-indents>ul>li{padding-left:1.6em;text-indent:-1.6em}}.mw-parser-output .refbegin-columns{margin-top:0.3em}.mw-parser-output .refbegin-columns ul{margin-top:0}.mw-parser-output .refbegin-columns li{page-break-inside:avoid;break-inside:avoid-column}@media screen{.mw-parser-output .refbegin{font-size:90%}}

/* end https://en.wikipedia.org/ */

</style><div class="refbegin" style="">

<ul><li><a href="https://en.wikiversity.org/wiki/Uninformed_Search_Project" class="extiw external" title="wikiversity:Uninformed Search Project">Uninformed Search Project</a> at the <a href="Wikiversity" title="Wikiversity">Wikiversity</a>.</li></ul>

</div>

/* start https://en.wikipedia.org/ */

.mw-parser-output .hlist dl,.mw-parser-output .hlist ol,.mw-parser-output .hlist ul{margin:0;padding:0}.mw-parser-output .hlist dd,.mw-parser-output .hlist dt,.mw-parser-output .hlist li{margin:0;display:inline}.mw-parser-output .hlist.inline,.mw-parser-output .hlist.inline dl,.mw-parser-output .hlist.inline ol,.mw-parser-output .hlist.inline ul,.mw-parser-output .hlist dl dl,.mw-parser-output .hlist dl ol,.mw-parser-output .hlist dl ul,.mw-parser-output .hlist ol dl,.mw-parser-output .hlist ol ol,.mw-parser-output .hlist ol ul,.mw-parser-output .hlist ul dl,.mw-parser-output .hlist ul ol,.mw-parser-output .hlist ul ul{display:inline}.mw-parser-output .hlist .mw-empty-li{display:none}.mw-parser-output .hlist dt::after{content:": "}.mw-parser-output .hlist dd::after,.mw-parser-output .hlist li::after{content:" · ";font-weight:bold}.mw-parser-output .hlist dd:last-child::after,.mw-parser-output .hlist dt:last-child::after,.mw-parser-output .hlist li:last-child::after{content:none}.mw-parser-output .hlist dd dd:first-child::before,.mw-parser-output .hlist dd dt:first-child::before,.mw-parser-output .hlist dd li:first-child::before,.mw-parser-output .hlist dt dd:first-child::before,.mw-parser-output .hlist dt dt:first-child::before,.mw-parser-output .hlist dt li:first-child::before,.mw-parser-output .hlist li dd:first-child::before,.mw-parser-output .hlist li dt:first-child::before,.mw-parser-output .hlist li li:first-child::before{content:" (";font-weight:normal}.mw-parser-output .hlist dd dd:last-child::after,.mw-parser-output .hlist dd dt:last-child::after,.mw-parser-output .hlist dd li:last-child::after,.mw-parser-output .hlist dt dd:last-child::after,.mw-parser-output .hlist dt dt:last-child::after,.mw-parser-output .hlist dt li:last-child::after,.mw-parser-output .hlist li dd:last-child::after,.mw-parser-output .hlist li dt:last-child::after,.mw-parser-output .hlist li li:last-child::after{content:")";font-weight:normal}.mw-parser-output .hlist ol{counter-reset:listitem}.mw-parser-output .hlist ol>li{counter-increment:listitem}.mw-parser-output .hlist ol>li::before{content:" "counter(listitem)"\a0 "}.mw-parser-output .hlist dd ol>li:first-child::before,.mw-parser-output .hlist dt ol>li:first-child::before,.mw-parser-output .hlist li ol>li:first-child::before{content:" ("counter(listitem)"\a0 "}

/* end https://en.wikipedia.org/ */

</style><style data-mw-deduplicate="TemplateStyles:r1236075235">

/* start https://en.wikipedia.org/ */

.mw-parser-output .navbox{box-sizing:border-box;border:1px solid #a2a9b1;width:100%;clear:both;font-size:88%;text-align:center;padding:1px;margin:1em auto 0}.mw-parser-output .navbox .navbox{margin-top:0}.mw-parser-output .navbox+.navbox,.mw-parser-output .navbox+.navbox-styles+.navbox{margin-top:-1px}.mw-parser-output .navbox-inner,.mw-parser-output .navbox-subgroup{width:100%}.mw-parser-output .navbox-group,.mw-parser-output .navbox-title,.mw-parser-output .navbox-abovebelow{padding:0.25em 1em;line-height:1.5em;text-align:center}.mw-parser-output .navbox-group{white-space:nowrap;text-align:right}.mw-parser-output .navbox,.mw-parser-output .navbox-subgroup{background-color:#fdfdfd}.mw-parser-output .navbox-list{line-height:1.5em;border-color:#fdfdfd}.mw-parser-output .navbox-list-with-group{text-align:left;border-left-width:2px;border-left-style:solid}.mw-parser-output tr+tr>.navbox-abovebelow,.mw-parser-output tr+tr>.navbox-group,.mw-parser-output tr+tr>.navbox-image,.mw-parser-output tr+tr>.navbox-list{border-top:2px solid #fdfdfd}.mw-parser-output .navbox-title{background-color:#ccf}.mw-parser-output .navbox-abovebelow,.mw-parser-output .navbox-group,.mw-parser-output .navbox-subgroup .navbox-title{background-color:#ddf}.mw-parser-output .navbox-subgroup .navbox-group,.mw-parser-output .navbox-subgroup .navbox-abovebelow{background-color:#e6e6ff}.mw-parser-output .navbox-even{background-color:#f7f7f7}.mw-parser-output .navbox-odd{background-color:transparent}.mw-parser-output .navbox .hlist td dl,.mw-parser-output .navbox .hlist td ol,.mw-parser-output .navbox .hlist td ul,.mw-parser-output .navbox td.hlist dl,.mw-parser-output .navbox td.hlist ol,.mw-parser-output .navbox td.hlist ul{padding:0.125em 0}.mw-parser-output .navbox .navbar{display:block;font-size:100%}.mw-parser-output .navbox-title .navbar{float:left;text-align:left;margin-right:0.5em}body.skin--responsive .mw-parser-output .navbox-image img{max-width:none!important}@media print{body.ns-0 .mw-parser-output .navbox{display:none!important}}

/* end https://en.wikipedia.org/ */

</style></div><div role="navigation" class="navbox" aria-labelledby="Data_structures_and_algorithms145" style="padding:3px"><table class="nowraplinks hlist mw-collapsible autocollapse navbox-inner" style="border-spacing:0;background:transparent;color:inherit"><tbody><tr><th scope="col" class="navbox-title" colspan="2"><style data-mw-deduplicate="TemplateStyles:r1239400231">

/* start https://en.wikipedia.org/ */

.mw-parser-output .navbar{display:inline;font-size:88%;font-weight:normal}.mw-parser-output .navbar-collapse{float:left;text-align:left}.mw-parser-output .navbar-boxtext{word-spacing:0}.mw-parser-output .navbar ul{display:inline-block;white-space:nowrap;line-height:inherit}.mw-parser-output .navbar-brackets::before{margin-right:-0.125em;content:"[ "}.mw-parser-output .navbar-brackets::after{margin-left:-0.125em;content:" ]"}.mw-parser-output .navbar li{word-spacing:-0.125em}.mw-parser-output .navbar a>span,.mw-parser-output .navbar a>abbr{text-decoration:inherit}.mw-parser-output .navbar-mini abbr{font-variant:small-caps;border-bottom:none;text-decoration:none;cursor:inherit}.mw-parser-output .navbar-ct-full{font-size:114%;margin:0 7em}.mw-parser-output .navbar-ct-mini{font-size:114%;margin:0 4em}html.skin-theme-clientpref-night .mw-parser-output .navbar li a abbr{color:var(--color-base)!important}@media(prefers-color-scheme:dark){html.skin-theme-clientpref-os .mw-parser-output .navbar li a abbr{color:var(--color-base)!important}}@media print{.mw-parser-output .navbar{display:none!important}}

/* end https://en.wikipedia.org/ */

</style><div id="Data_structures_and_algorithms145" style="font-size:114%;margin:0 4em"><a href="Data_structure" title="Data structure">Data structures</a> and <a href="Algorithm" title="Algorithm">algorithms</a></div></th></tr><tr><th scope="row" class="navbox-group" style="width:1%">Data structures</th><td class="navbox-list-with-group navbox-list navbox-odd" style="width:100%;padding:0"><div style="padding:0 0.25em">

<ul><li><a href="Array_(data_structure)" title="Array (data structure)">Array</a></li>

<li><a href="Associative_array" title="Associative array">Associative array</a></li>

<li><a href="Binary_search_tree" title="Binary search tree">Binary search tree</a></li>

<li><a href="Fenwick_tree" title="Fenwick tree">Fenwick tree</a></li>

<li><a href="Graph_(abstract_data_type)" title="Graph (abstract data type)">Graph</a></li>

<li><a href="Hash_table" title="Hash table">Hash table</a></li>

<li><a href="Linked_list" title="Linked list">Linked list</a></li>

<li><a href="Queue_(abstract_data_type)" title="Queue (abstract data type)">Queue</a></li>

<li><a href="Segment_tree" title="Segment tree">Segment tree</a></li>

<li><a href="Stack_(abstract_data_type)" title="Stack (abstract data type)">Stack</a></li>

<li><a href="String_(computer_science)" title="String (computer science)">String</a></li>

</div></td></tr><tr><th scope="row" class="navbox-group" style="width:1%">Algorithms and <a href="Algorithmic_paradigm" title="Algorithmic paradigm">algorithmic paradigms</a></th><td class="navbox-list-with-group navbox-list navbox-even" style="width:100%;padding:0"><div style="padding:0 0.25em">

<ul><li><a href="Backtracking" title="Backtracking">Backtracking</a></li>

<li><a href="Binary_search" title="Binary search">Binary search</a></li>

<li><a href="Breadth-first_search" title="Breadth-first search">Breadth-first search</a></li>

<li><a href="Brute-force_search" title="Brute-force search">Brute-force search</a></li>

<li><a href="Depth-first_search" title="Depth-first search">Depth-first search</a></li>

<li><a href="Divide-and-conquer_algorithm" title="Divide-and-conquer algorithm">Divide and conquer</a></li>

<li><a href="Dynamic_programming" title="Dynamic programming">Dynamic programming</a></li>

<li><a href="Graph_traversal" title="Graph traversal">Graph traversal</a></li>

<li><a href="Greedy_algorithm" title="Greedy algorithm">Greedy</a></li>

<li><a href="Hash_function" title="Hash function">Hash function</a></li>

<li><a href="Minimax" title="Minimax">Minimax</a></li>

<li><a href="Online_algorithm" title="Online algorithm">Online</a></li>

<li><a href="Randomized_algorithm" title="Randomized algorithm">Randomized</a></li>

<li><a href="Recursion_(computer_science)" title="Recursion (computer science)">Recursion</a></li>

<li><a href="Root-finding_algorithm" title="Root-finding algorithm">Root-finding</a></li>

<li><a href="Sorting_algorithm" title="Sorting algorithm">Sorting</a></li>

<li><a href="Streaming_algorithm" title="Streaming algorithm">Streaming</a></li>

<li><a href="Sweep_line_algorithm" title="Sweep line algorithm">Sweep line</a></li>

<li><a href="String-searching_algorithm" title="String-searching algorithm">String-searching</a></li>

<li><a href="Topological_sorting" title="Topological sorting">Topological sorting</a></li></ul>

</div></td></tr><tr><td class="navbox-abovebelow" colspan="2"><div>

<ul><li><a href="List_of_data_structures" title="List of data structures">List of data structures</a></li>

<li><a href="List_of_algorithms" title="List of algorithms">List of algorithms</a></li></ul>

</div></td></tr></tbody></table></div></div><div><div class="zim-footer">

This article is issued from <a class="external text" title="Last edited on 2025-02-10" href="https://en.wikipedia.org/wiki/?title=Search_algorithm&oldid=1275014315">Wikipedia</a>. The text is available under <a class="external text" href="https://creativecommons.org/licenses/by-sa/4.0/deed.en">Creative Commons Attribution-Share Alike 4.0</a> unless otherwise noted. Additional terms may apply for the media files.

</div>

</div></div>

</div>

</main>

</div>

</body></html>